home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / C / Applications / Moscow ML 1.31 / source code / mosml / src / mosmllib / Splaytree.sig < prev    next >
Encoding:
Text File  |  1996-07-03  |  758 b   |  26 lines  |  [TEXT/R*ch]
  1. (* Splaytree -- Splay tree structure supporting Splaymap and Splayset.
  2.  * 
  3.  * Modified for Moscow ML from SML/NJ library which is 
  4.  * COPYRIGHT (c) 1993 by AT&T Bell Laboratories.  
  5.  * See file mosml/copyrght/copyrght.att for details.
  6.  *)
  7.  
  8. datatype 'a splay = 
  9.     SplayObj of {value : 'a,
  10.          right : 'a splay,
  11.          left  : 'a splay}
  12.   | SplayNil
  13.  
  14. val splay : ('a -> ordering) * 'a splay -> ordering * 'a splay
  15. val join  : 'a splay * 'a splay -> 'a splay
  16.  
  17. (* [splay (cmp,tree)] returns (r,tree') 
  18.    where tree' is tree adjusted using the comparison function cmp
  19.    and, if tree' = SplayObj{value,...}, then r = cmp value.
  20.    tree' = SplayNil iff tree = SplayNil, in which case r is undefined.
  21.  
  22.    [join(t,t')] returns a new splay tree formed of t and t'
  23. *)
  24.  
  25.  
  26.